The disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office patent file or records, once a patent is issued on this application, but otherwise reserves all copyright rights whatsoever.
This invention relates to methods for rendering shapes, and particularly to such methods that are automated.
The ability to determine the position and/or attitude of an object is of considerable practical importance in many applications, including industrial manufacturing, robot guidance, intelligent transportation systems, mail and parcel handling, and many others. Position might include up to three degrees of freedom (e.g., up-down, in-out, and side-ways), and the three degrees of freedom of attitude (e.g., pitch, yaw, and roll). Together, these six degrees of freedom can be used to describe what can be referred to as the xe2x80x9clocationxe2x80x9d or xe2x80x9cposexe2x80x9d of an object. Note that here, xe2x80x9clocationxe2x80x9d or xe2x80x9cposexe2x80x9d can mean more than just position in three spatial dimensionsxe2x80x94it can also include information as to the other non-translational degrees of freedom, such as skew, perspective, aspect-ratio, and many other more exotic non-translational degrees of freedom. In a two-dimensional plane, position includes two translation degrees of freedom (e.g., up-down and side-ways), and at least one non-translation degree of freedom, such as xe2x80x9corientationxe2x80x9d (a rotation degree of freedom), and possibly skew, aspect ratio, size, and others.
It is well-known to use machine vision to locate objects at a distance. A digital image of a scene containing an object to be located is formed by any suitable apparatus, for example consisting of visible light illumination, a CCD camera, and a video digitizer. The digital image is then analyzed by a suitable image analysis device, for example consisting of a digital signal processor or personal computer running software that implements a suitable method for identifying and locating image patterns that correspond to the object of interest. The analysis results in certain parameters that describe the pattern in the image that corresponds to the object, or a suitable portion of the object, in the scene. These parameters might include position, attitude, and size of the pattern in the image. These parameters are then used to compute the location (pose) of the object using well-known mathematical formulas.
There are many methods known in the art for analyzing digital images to determine one or more of the pattern parameters, including blob analysis, normalized correlation, Hough transforms, and geometric pattern matching. Numerous other methods have been used or proposed in commercial practice or in academic literature.
The process of determining object location (pose) by machine vision can be referred to in various ways, including xe2x80x9calignmentxe2x80x9d, xe2x80x9cregistrationxe2x80x9d, xe2x80x9cpattern recognitionxe2x80x9d, and xe2x80x9cpattern matchingxe2x80x9d. For present purposes herein, those terms are equivalent, and so herein the term xe2x80x9calignmentxe2x80x9d shall be used to refer to any such process. Any object, or portion of an object, that gives rise to the pattern in the image to be analyzed shall be called an xe2x80x9calignment targetxe2x80x9d, or simply a xe2x80x9ctargetxe2x80x9d.
Most machine vision alignment applications require locating targets having a shape determined by engineering considerations that are largely independent of the needs of automated visual alignment. In these cases, the objects contain no special markings or components specially adapted to aid the alignment method. Consequently, the alignment method must work with whatever object shape is given. There are many applications, however, where the alignment target can be engineered specifically for that purpose. Examples include fiducial marks on printed circuit boards, registration marks etched on silicon wafers, and xe2x80x9cbull""s eyexe2x80x9d targets used by the United Parcel Service on package labels. A target that has been engineered to aid machine vision alignment can be called a xe2x80x9ccooperative target.xe2x80x9d In contexts where it is clear that a target has been engineered for alignment, the modifier xe2x80x9ccooperativexe2x80x9d is sometimes omitted, but xe2x80x9ccooperativexe2x80x9d is understood.
Although alignment methods have an extensive literature and commercial history, relatively little work has been done on understanding the effect of target shape on alignment performance. The work is almost entirely restricted to shapes composed of circles and polygons, to the effect of such shapes on binary image analysis methods, to translation-only (i.e., horizontal and vertical) alignment, and to accuracy criteria only.
Rotationally symmetric targets, primarily circles and xe2x80x9cbull""s-eyexe2x80x9d patterns, have long been a favorite in the academic literature. In a 1974 paper, for example, W. Makous xe2x80x9cOptimal Patterns for Alignmentxe2x80x9d, in Applied Optics, Vol. 13, No. 3, states that xe2x80x9ca bull""s-eye pattern of regularly alternating black and white rings would be optimal for visual alignment in two dimensions.xe2x80x9d Twenty four years later, in a 1998 paper entitled xe2x80x9cDesign of Shapes for Precise Image Registrationxe2x80x9d, in IEEE Trans. on Information Theory, Vol. 44, No. 7, Bruckstein, O""Gorman, and Orlitsky state that xe2x80x9cExperimental tests and . . . theoretical developments . . . led to the conclusion that the xe2x80x98bull""s-eyexe2x80x99 fiducial is indeed a very good, robust and practical location mark.xe2x80x9d
Rotationally symmetric targets suffer from a number of limitations, however, that have not been anticipated in the prior art. First, such targets contain no information for measuring orientation. This has been considered an advantage, based on the assumption that alignment methods would fail under orientation misalignment unless the target is rotationally symmetric, but the recent advent of practical methods for orientation alignment have created a need for targets that convey substantial orientation information.
A second limitation of rotationally symmetric targets, such as the xe2x80x9cbull""s eyexe2x80x9d pattern, is that circles and arcs of circles are extremely common in manufactured items, and one cannot guarantee that such shapes will not appear in the field of view containing the target. The appearance of such a shape in the same field of view as a target composed of circles or arcs of circles results in potential confusion for the alignment method, and this confusion usually leads to higher recognition error rates under variations in image quality typically encountered in an industrial environment.
A third limitation of rotationally symmetric targets is that they are often not good choices for measuring size, what might be called xe2x80x9csize alignmentxe2x80x9d. While such a target does contain plenty of information for conveying size, the concentric circular boundaries match each other perfectly at many different sizes. At the correct size the overall target match will be higher than at any of the wrong sizes, but the matches at the wrong sizes are sometimes good enough to create confusion under realistic conditions of image degradation. This xe2x80x9cself-confusionxe2x80x9d can lead to higher recognition error rates. Furthermore, this self-confusion generally requires that any practical alignment method must examine the xe2x80x9csizexe2x80x9d degree of freedom more carefully to avoid error, which increases recognition time.
The academic literature has also considered using as alignment targets simple polygons such as squares and diamonds, as well as complex sequences of stripes that are optimal for 1D or 2D alignment in some theoretical sense, but are almost impossible to manufacture.
Known targets in commercial use include simple geometric shapes such as circles, bull""s-eyes, squares, crosses, two squares touching at a corner, and patterns consisting of a cross embedded in a circle.
In the semiconductor industry, significant attention has been given to the engineering of targets used to achieve the extreme accuracy needed to register the many layers created during wafer processing. Early targets consisted of interleaved comb structures, which were used by human operators in manual alignment systems prior to the advent of machine vision alignment. More recently, manufacturers have used squares, concentric xe2x80x9cbox-in-boxxe2x80x9d shapes, crosses, circles, rings, bull""s-eyes, and various other shapes comprised of rectilinear or circular features. Much of the prior art in semiconductors is concerned with process issues such as 3D structure, edge profiles, circuit design rules, and resist flow.
Prior art cooperative targets suffer from one or more of the following limitations:
Target features are sometimes inadequate for providing sufficient information regarding non-translation degrees of freedom (e.g., orientation and size).
Reduced information is available when straight-line features are aligned (accidentally or otherwise) with the pixel grid.
Confusion and consequent reduced reliability result from use of circles, circular arcs, line segments, or right angles, which are common in manufactured objects, and therefore may be confused by the alignment method with other patterns in the scene.
Reduced reliability results from use of fine target features that do not survive a manufacturing process.
Confusion and consequent reduced reliability result from target shapes that are xe2x80x9cself-confusingxe2x80x9d, i.e., that match themselves too well when translated, rotated, or changed in size.
Reduced alignment speed results from target shapes that cannot be identified unambiguously by their coarsest features.
For a number of reasons these limitations generally have not been serious for past use of machine vision. The alignment methods that have been available in the past, such as blob analysis and normalized correlation, had not been accurate enough (i.e., could extract only limited information from an image) to expose subtle limitations of the targets. Few practical methods existed for determining non-translation degrees of freedom, and those that were known were not widely used due to cost, reliability, or performance problems. Machine vision was often a new and challenging manufacturing technology, and so emphasis was placed on basic functionality and not on squeezing high performance from the equipment. In electronics and semiconductor applications, among the largest users of machine vision, the coarser device geometries of the past placed limited demands on machine vision alignment.
Recent developments have created a need for a new breed of cooperative targets:
The commercial availability of practical, highly accurate alignment methods capable of aligning non-translation degrees of freedom, including orientation and size, has created a need for targets engineered to provide sufficient information in all such degrees of freedom.
Expanding experience with machine vision alignment has shown that increased error rates often result from targets that can be confused with similar shapes in the field of view, or are self-confusing in one or more degrees of freedom. Thus, there is a need for targets not based on common features such as lines, right-angles, and circles, and for targets specifically engineered to minimize or eliminate self-confusion in all degrees of freedom.
Shrinking sizes and tighter tolerances in manufactured goods, particularly in semiconductors and electronics, are placing increasing demands on accuracy, speed, and robustness of machine vision alignment. Consequently, there is a need to reconsider the often-neglected role of target shape, and produce targets that cooperate with practical alignment methods to achieve best performance.
The need for new cooperative targets not subject to the limitations of the prior art leads to a need for new methods for engineering such targets. Prior art methods for engineering targets suffer from one or more of the following limitations:
The known target engineering methods address only translation alignment, not other degrees of freedom such as orientation and size.
The known target engineering methods are based on a theoretical analysis of absolute accuracy, which to avoid intractable complexity, requires unrealistic simplifying assumptions about image quality, requires that target shape be restricted to simple shapes composed of circles and rectilinear edges, and requires the use of simple binary alignment methods, such as blob centroid.
The known target engineering methods do not consider alignment speed.
The known target engineering methods do not consider alignment reliability under practical conditions of image variation and process degradation.
The known target engineering methods do not consider confusion with other patterns and self-confusion.
Consequently there is a need for a new method for engineering alignment targets.
Another factor contributing to reduced performance of known cooperative alignment targets is insufficient precision in known methods for rendering such targets. Without the ability to render a cooperative alignment target at very high precision, an alignment target engineered to address the problems of the prior art would not perform optimally. Consequently, it is necessary to be able to render such targets in various forms, including bitmap images, at very high precision. In the prior art, methods for rendering shapes accurately on a discrete grid have been studied extensively for graphics applications, where they are generally referred to as anti-aliasing methods. These methods produce pleasing graphics for human observation, but achieving the extreme accuracy and flexibility needed for machine vision alignment applications is difficult.
In the machine vision prior art, several methods have been used to render binary shapes on discrete grids. In one method, pixels along the shape boundary are given a gray value corresponding to the fraction of the pixel""s area that falls on either side of the boundary. This method suffers from several limitations:
The computations are complex, resulting in very slow rendering that makes automated testing using thousands of synthetically generated images impractical.
The method assumes an unrealistically ideal sensor model, resulting in loss of accuracy. Attempts to improve the sensor model by post-processing the rendered image are also limited in accuracy due to grid quantization.
The method is impractical for complex shapes that are not composed of straight-line segments.
In another known rendering method, a binary image is rendered at much higher resolution than that needed for the target rendering. This high-resolution image is then filtered and sub-sampled to produce the final rendering. While such a method can be quite accurate in principal, computer time and memory limitations make truly high accuracy impractical.
It is well-known in the prior art to cause a cooperative target to appear on an object to be located, place the object within the field of view of a camera or other suitable image formation device, capture an image of the object bearing the target, and analyze the image using an alignment method to determine the x-y position of the target in the image.
The invention includes a method and apparatus for locating objects by means of machine vision alignment using cooperative targets. The method and apparatus provides significant improvements over the prior art. In one general aspect, the invention uses novel cooperative targets that have substantial performance advantages over those used in the prior art. In another general aspect, the invention uses alignment methods having non-translation alignment capabilities, such as geometric pattern recognition, cooperating with suitable targets to perform alignment in non-translation degrees of freedom, such as orientation and size.
The invention includes a novel set of criteria for evaluating alignment targets for accuracy, speed, yield (robustness), and ease of use. The accuracy criteria of the invention are based on a quantitative analysis of target boundary shape that has several advantages over prior art methods:
The accuracy criteria of the invention can be used for essentially arbitrary shapes;
The accuracy criteria of the invention provide estimates of the information content of a cooperative target, independent of any specific alignment method; and
The accuracy criteria of the invention can evaluate targets for their capacity to accurately align non-translation degrees of freedom, such as orientation and size.
The accuracy criteria of the invention also include a quantitative measure of the tendency of a target to contribute to loss of accuracy due to accidental alignment with the pixel grid of the machine vision system, a phenomenon referred to herein as xe2x80x9cgrid degeneracyxe2x80x9d. This phenomenon has been recognized in academic research, although useful remedies appear not to have been investigated, and many cooperative targets in current use suffer from this problem.
Although speed criteria are apparently unknown in the prior art, an aspect of the invention includes qualitative criteria based on certain common characteristics of most practical alignment methods in use, which are in turn loosely based on principals of information content.
Yield criteria are also apparently unknown in the prior art, with the exception of targets used for wafer fabrication in the semiconductor industry, where the criteria are specific to wafer processing. For high yield (low error rates), an aspect of the invention considers the ability to survive manufacturing processes and other environmental conditions. Another aspect of the invention includes criteria relating to potential errors caused by self-confusion and background confusion.
The ease-of-use criteria of the invention require that targets be easy to render on the objects to be located, easy to teach to the machine vision alignment method, and easy to analyze using the criteria of the invention. To satisfy these ease-of-use criteria, the invention uses targets that are defined by a set of algebraic formulas.
The invention includes a novel method of accurately rendering algebraically defined shapes that can be used to render alignment targets, or for other purposes. The method can render shapes as a bitmap image for machine vision alignment training, for computer display for human observation, and for computer printout for documentation. The method can aid in rendering targets on the objects to be located by providing input to a computer-aided design (CAD) system, or by directly controlling devices such as laser engravers. The rendering method of the invention is fast, extremely accurate, and can handle substantially arbitrary shapes.
The rendering method according to the invention includes two key steps: first, targets are defined by a real-valued function of position in the real plane that gives the distance from that position to the nearest point on a target boundary. The function gives distance as a positive value for points inside the figure, and as a negative value for points outside the figure; and second, an edge model is used to map distance to real-valued image intensity. By choosing appropriate edge model parameters, edge sharpness, focus, video gain, and noise can be modeled. Other steps are used with these two key steps to provide a complete rendering method. In a preferred embodiment, the rendering method of the invention uses high-precision floating point arithmetic to estimate real-valued functions on the real plane, and only converts to a discrete grid as the final step. The result is the ability to control the position, orientation, and size of the final rendering to extremely high precision.
The invention includes a novel method for engineering alignment targets that satisfy the above set of criteria of the invention. By contrast, known methods generally try to analyze a set of specific shapes, such as a circle, square, and diamond, and then simply choose the best one. Alternatively, in some known methods, a single parameter such as aspect ratio might be optimized according to some criteria. The method of the invention for engineering alignment targets, by contrast, starts with a simple shape and then refines the initial shape in a series of steps, where each such step produces a different shape, derived from the previous step, that resolves some deficiency of that shape.
In one embodiment of the method for engineering alignment targets, the initial shape contains radial features, which carry orientation information but not size, and circular features, which carry size information but not orientation. As recognized by the invention, this independence of radial and circular features allows orientation and size performance to be adjusted independently.
In another embodiment of the method, the starting shape is defined algebraically using polar coordinates. In a preferred embodiment, the starting shape is a xe2x80x9cfanxe2x80x9d.
In a preferred embodiment, the series of steps includes at least one step whose purpose is to achieve at least one of the following goals:
Increase boundary perimeter to improve accuracy. In a preferred embodiment, perimeter is increased by adding holes.
Balance orientation and size accuracy, so that the target is not overly biased towards one degree of freedom at the expense of the other.
Reduce or eliminate rotational symmetry.
Reduce or eliminate orientation self-similarity.
Reduce or eliminate size self-similarity.
Reduce or eliminate grid degeneracy.
Reduce or eliminate features that are common in manufactured items, such as circles, circular arcs, straight lines, and right angles.
The alignment target engineering method of the invention provides at least the following benefits:
The alignment target engineering method of the invention allows objective, quantitative comparison of the ability of different shapes to convey alignment information in all relevant degrees of freedom, including translation, orientation, and size.
The alignment target engineering method of the invention avoids fruitless theoretical attempts to determine absolute accuracy, and instead allows analysis of arbitrary shapes with no assumptions about image quality or the alignment method to be used.
The alignment target engineering method of the invention takes into account the effect of target shape on the speed of practical alignment methods in common use.
The alignment target engineering method of the invention takes into account the effect of potential confusion with other patterns, and self-confusion, on alignment reliability.
The invention includes specific alignment targets that have at least one of the following attributes:
They satisfy the invention""s evaluation criteria.
They result from the use of the invention""s engineering method.
They have no significant rotational symmetry.
They have no significant orientation or size self-similarity.
They are not primarily composed of circles, circular arcs, straight lines, or right angles.
In one embodiment, the specific alignment targets are shapes consisting of at least one xe2x80x9cgeneralized polar polygon.xe2x80x9d A generalized polar polygon is a plane figure that is a polygon with optionally rounded vertices when drawn in polar coordinates, keeping in mind that all coordinates (r, xcex8+360xc2x0 n), for integer n, are the same point. Such a figure will include radial lines, circular arcs, and spiral segments when drawn in the Cartesian plane.
In another embodiment, the specific alignment targets are members of a family of xe2x80x9cfanxe2x80x9d shapes.
In a preferred embodiment, the targets are fan shapes that satisfy all, or almost all, of the evaluation criteria established by the invention. These are novel shapes that have no prior history in mathematics or practical arts. Any target that substantially satisfies all of the evaluation criteria is called a xe2x80x9cUniversal Alignment Targetxe2x80x9d (UAT).